class LinkedList {
    // 初始链表长度为 0
    length = 0;

    // 初始 head 为 null，head 指向链表的第一个节点
    head = null;

    // 内部类（链表里的节点 Node）
    Node = class {
      data;
      next = null;

      constructor(data) {
        this.data = data;
      }
    };

    // ------------ 链表的常见操作 ------------ //

    // append() 往链表尾部追加数据
    append(data) {
      // 1、创建新节点
      const newNode = new this.Node(data);

      // 2、追加新节点
      if (this.length === 0) {
        // 链表长度为 0 时，即只有 head 的时候
        this.head = newNode;
      } else {
        // 链表长度大于 0 时，在最后面添加新节点
        let currentNode = this.head;

        // 当 currentNode.next 不为空时，
        // 循序依次找最后一个节点，即节点的 next 为 null 时
        while (currentNode.next !== null) {
          currentNode = currentNode.next;
        }

        // 最后一个节点的 next 指向新节点
        currentNode.next = newNode;
      }

      // 3、追加完新节点后，链表长度 + 1
      this.length++;
    }

    // insert() 在指定位置（position）插入节点
    insert(position, data) {
      // position 新插入节点的位置
      // position = 0 表示新插入后是第一个节点
      // position = 1 表示新插入后是第二个节点，以此类推

      // 1、对 position 进行越界判断，不能小于 0 或大于链表长度
      if (position < 0 || position > this.length) return false;

      // 2、创建新节点
      const newNode = new this.Node(data);

      // 3、插入节点
      if (position === 0) {
        // position = 0 的情况
        // 让新节点的 next 指向 原来的第一个节点，即 head
        newNode.next = this.head;

        // head 赋值为 newNode
        this.head = newNode;
      } else {
        // 0 < position <= length 的情况

        // 初始化一些变量
        let currentNode = this.head; // 当前节点初始化为 head
        let previousNode = null; // head 的 上一节点为 null
        let index = 0; // head 的 index 为 0

        // 在 0 ~ position 之间遍历，不断地更新 currentNode 和 previousNode
        // 直到找到要插入的位置
        while (index++ < position) {
          previousNode = currentNode;
          currentNode = currentNode.next;
        }

        // 在当前节点和当前节点的上一节点之间插入新节点，即它们的改变指向
        newNode.next = currentNode;
        previousNode.next = newNode;
      }

      // 更新链表长度
      this.length++;
      return newNode;
    }

    // getData() 获取指定位置的 data
    getData(position) {
      // 1、position 越界判断
      if (position < 0 || position >= this.length) return null;

      // 2、获取指定 position 节点的 data
      let currentNode = this.head;
      let index = 0;

      while (index++ < position) {
        currentNode = currentNode.next;
      }

      // 3、返回 data
      return currentNode.data;
    }

    // indexOf() 返回指定 data 的 index，如果没有，返回 -1。
    indexOf(data) {
      let currentNode = this.head;
      let index = 0;

      while (currentNode) {
        if (currentNode.data === data) {
          return index;
        }
        currentNode = currentNode.next;
        index++;
      }

      return -1;
    }

    // update() 修改指定位置节点的 data
    update(position, data) {
      // 涉及到 position 都要进行越界判断
      // 1、position 越界判断
      if (position < 0 || position >= this.length) return false;

      // 2、痛过循环遍历，找到指定 position 的节点
      let currentNode = this.head;
      let index = 0;
      while (index++ < position) {
        currentNode = currentNode.next;
      }

      // 3、修改节点 data
      currentNode.data = data;

      return currentNode;
    }

    // removeAt() 删除指定位置的节点
    removeAt(position) {
      // 1、position 越界判断
      if (position < 0 || position >= this.length) return null;

      // 2、删除指定 position 节点
      let currentNode = this.head;
      if (position === 0) {
        // position = 0 的情况
        this.head = this.head.next;
      } else {
        // position > 0 的情况
        // 通过循环遍历，找到指定 position 的节点，赋值到 currentNode

        let previousNode = null;
        let index = 0;

        while (index++ < position) {
          previousNode = currentNode;
          currentNode = currentNode.next;
        }

        // 巧妙之处，让上一节点的 next 指向到当前的节点的 next，相当于删除了当前节点。
        previousNode.next = currentNode.next;
      }

      // 3、更新链表长度 -1
      this.length--;

      return currentNode;
    }

    // remove() 删除指定 data 的节点
    remove(data) {
      this.removeAt(this.indexOf(data));
    }

    // isEmpty() 判断链表是否为空
    isEmpty() {
      return this.length === 0;
    }

    // size() 获取链表的长度
    size() {
      return this.length;
    }

    // toString() 链表数据以字符串形式返回
    toString() {
      let currentNode = this.head;
      let result = "";

      // 遍历所有的节点，拼接为字符串，直到节点为 null
      while (currentNode) {
        result += currentNode.data + " ";
        currentNode = currentNode.next;
      }

      return result;
    }
}